package com.base.binarytree;

import java.util.Stack;

/**
 * 剑指 Offer 33. 二叉搜索树的后序遍历序列,
 * <p>
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 *
 * @author leon
 * @date 2021年09月23日 20:43
 */
public class VerifyPostorder {
    /**
     * 递归+分治
     * 二叉搜索树满足：
     * 1、左子树<根 和  右子树>根
     * 2、左右子树都是二叉搜索树
     * <p>
     * 后序遍历的数满足：
     * 最后一个树是树的根结点
     * <p>
     * 结合二叉搜索树与后序遍历，我们可以知道树的根结点和左右子树，根结点简单，关键在于区分左右子树，
     * 由于二差树的第一个特性，我们可以从前向后遍历这个树，当出现大于根结点的值时，此时值必然是左右子树的分割点。
     * 那么当我们找到左右子树后，我们要做的就只需要去判断左右子树是否满足第一个条件（只需要判断右子树所有值>根即可，因为找分割点时已经判断了左子树）
     * 当满足二叉搜索树的条件一后，我们只需要递归的判断它的左右子树是否满足条件二即可
     *
     *
     * 递归：
     *      终止条件：当前数组里面没有元素时，或者只有一个元素，也就是i>=j
     *      递推过程：
     *           1、判断左树是否是一个二叉搜索树
     *           2、判断右子树是否是一个二叉搜索树
     *
     *
     * @param postorder 后序遍历的树
     * @return 是否满足后序遍历的二叉搜索树条件
     */
    public boolean verifyPostorder(int[] postorder) {
            return verifyPostorder(postorder,0,postorder.length-1);
    }

    public boolean verifyPostorder(int[] postorder,int start,int end){
        if (start>=end){
            return true;
        }
        int pointer = start;
        while (postorder[pointer]<postorder[end]){
            pointer++;
        }
        int m = pointer - 1;
        while (postorder[pointer]>postorder[end]){
            pointer++;
        }
        return pointer==end&&verifyPostorder(postorder,start,m)&&verifyPostorder(postorder,m+1,end-1);
    }

    /**
     * 辅助单调栈
     作者：jyd
     链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/solution/mian-shi-ti-33-er-cha-sou-suo-shu-de-hou-xu-bian-6/
     来源：力扣（LeetCode）
     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param postorder
     * @return
     */
    public boolean verifyPostorder1(int[] postorder) {
            Stack<Integer> stack = new Stack<>();
            int root = Integer.MAX_VALUE;
            for(int i = postorder.length - 1; i >= 0; i--) {
                if(postorder[i] > root) return false;
                while(!stack.isEmpty() && stack.peek() > postorder[i])
                    root = stack.pop();
                stack.add(postorder[i]);
            }
            return true;
        }

}
